﻿#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1, 0); // dp[i] 表⽰：当结点的数量为 i 个的时候，⼀共有多少颗 BST
        dp[0] = 1; // 空树也是⼀颗⼆叉搜索树
        for (int i = 1; i <= n; i++) // 枚举结点的总数
            for (int j = 1; j <= i; j++) // 选择每⼀个根节点
                dp[i] += dp[j - 1] * dp[i - j]; // ⼆叉树总量累加在⼀起

        return dp[n];
    }
};

int main()
{

    cout << Solution().numTrees(3) << endl;

    return 0;
}


